#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int Vertex; /* 顶点编号类型 */
typedef int GElemSet; /* 边权重类型 */
typedef char VertInfo; /* 顶点信息类型 */
typedef struct MGraphNode *MGraph; /* 邻接矩阵表示的图 */
struct MGraphNode {
    int n_verts; /* 顶点数 */
    int m_edges; /* 边数 */
    GElemSet **edge_matrix;/* 邻接矩阵 */
    VertInfo *ver_list; /* 存储顶点信息 */
    GElemSet no_edge_value; /* 表述没有边时的权重值 */
    bool directed; /* true为有向图，false为无向图 */
};
#define NIL -1      /* 顶点不存在时的返回值 */
#define kMaxV 100   /* 最多顶点数 */
#define kMaxNum 1e9 /* 大于最大距离值的数字 */

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed);
bool ExistEdge(MGraph graph, Vertex u, Vertex v);
void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight);
MGraph BuildGraph();

/* 算法8-3: 求所有点对间最短路的Floyd-Warshall算法 FloydWarshall (graph, path, dist) */
void FloydWarshall(MGraph graph, Vertex path[][kMaxV], GElemSet dist[][kMaxV]) {
    int n;
    Vertex i, j, k;

    n = graph->n_verts;
    for (i = 0; i < n;
            i++) { /* 初始化各对顶点之间的已知路径和距离 */
        for (j = 0; j < n; j++) {
            dist[i][j] = graph->edge_matrix[i][j];
            path[i][j] = NIL;
        }
    }
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] <
                        dist[i][j]) { /* 从vi经过vk到vj的一条路径更短 */
                    dist[i][j] = dist[i][k] + dist[k][j];
                    path[i][j] = k;
                }
            }
        }
    }
}
/* 算法8-3 结束 */

int main(void) {
    MGraph graph;
    Vertex u, v;
    GElemSet dist[kMaxV][kMaxV];
    Vertex path[kMaxV][kMaxV];

    graph = BuildGraph();
    FloydWarshall(graph, path, dist);
    printf("dist:\n");
    for (u = 0; u < graph->n_verts; u++) {
        for (v = 0; v < graph->n_verts; v++) {
            printf("%d ", dist[u][v]);
        }
        printf("\n");
    }
    printf("path:\n");
    for (u = 0; u < graph->n_verts; u++) {
        for (v = 0; v < graph->n_verts; v++) {
            printf("%d ", path[u][v]);
        }
        printf("\n");
    }
    return 0;
}

void InitGraph(MGraph graph, int kMaxVertex, GElemSet no_edge_value,
               bool directed) {
    /* 初始化一个空的图 */
    GElemSet *array;
    int i;
    Vertex u, v;

    graph->n_verts = 0;
    graph->m_edges = 0;
    /* 声明二维数组graph->edge_matrix[kMaxVertex][kMaxVertex] */
    array = (GElemSet *)malloc(sizeof(GElemSet) * kMaxVertex * kMaxVertex);
    graph->edge_matrix = (GElemSet **)malloc(sizeof(GElemSet *) * kMaxVertex);
    for (i = 0; i < kMaxVertex; i++) {
        graph->edge_matrix[i] = &array[i * kMaxVertex];
    }
    /* 声明顶点信息数组graph->ver_list[kMaxVertex] */
    graph->ver_list = (VertInfo *)malloc(sizeof(VertInfo) * kMaxVertex);
    graph->no_edge_value = no_edge_value;
    graph->directed = directed;
    for (u = 0; u < kMaxVertex; u++) {
        for (v = 0; v < kMaxVertex; v++) {
            graph->edge_matrix[u][v] = graph->no_edge_value;
        }
        graph->edge_matrix[u][u] =
            0; /* 最短路问题中假设原地不动距离为0 */
    }
}

bool ExistEdge(MGraph graph, Vertex u, Vertex v) {
    bool ret = false;

    if (u < graph->n_verts && v < graph->n_verts) {
        if (u != v && graph->edge_matrix[u][v] != graph->no_edge_value) {
            ret = true;
        }
    }
    return ret;
}

void InsertEdge(MGraph graph, Vertex u, Vertex v, GElemSet weight) {
    if (ExistEdge(graph, u, v) == false) {
        graph->edge_matrix[u][v] = weight;
        graph->m_edges++;
        if (graph->directed == false) {
            graph->edge_matrix[v][u] = weight;
        }
    }
}

MGraph BuildGraph() {
    MGraph graph;
    int n, m, i;
    Vertex u, v;
    GElemSet weight;

    graph = (MGraph)malloc(sizeof(struct MGraphNode));
    InitGraph(graph, kMaxV, kMaxNum, true);
    scanf("%d %d\n", &n, &m);
    graph->n_verts = n;
    for (i = 0; i < m; i++) {
        scanf("%d %d %d\n", &u, &v, &weight);
        InsertEdge(graph, u, v, weight);
    }
    return graph;
}